package ai;

import java.util.LinkedList;
import java.util.List;

import components.scenes.MapMatrix;
import components.scenes.Slot;

public class Pathfinder {

	public static Pathfinder instance = new Pathfinder();
	
	
	public List<Slot> findPath(MapMatrix map, Slot start, Slot end){
		LinkedList<LinkedList<Slot>> routes, correctRoutes;
		LinkedList<Slot> closed, startPath;
		routes = new LinkedList<LinkedList<Slot>>();
		correctRoutes = new LinkedList<LinkedList<Slot>>();
		
		closed = new LinkedList<Slot>();
		startPath = new LinkedList<Slot>();
		startPath.add(start);
		
		routes.add(startPath);
		
		while(!routes.isEmpty()){
			LinkedList<Slot> first = routes.poll();
			this.extend(map, routes, closed, first);
			this.findRoutes(routes, end, correctRoutes);
		}
		
		
		return correctRoute(correctRoutes);
		
	}
	
	private void findRoutes(LinkedList<LinkedList<Slot>> routes, Slot end,
			LinkedList<LinkedList<Slot>> correctRoutes) {
		
		for (LinkedList<Slot> route : routes){
			if (route.contains(end)){
				route.remove(0);
				correctRoutes.add(route);
			}
		}
		for (LinkedList<Slot> route : correctRoutes){
			routes.remove(route);
		}
		
	}

	public List<Slot> correctRoute(LinkedList<LinkedList<Slot>> routes) {
		if (routes.isEmpty()){
			return null;
		}
		List<Slot> candidate = routes.get(0);
		int best = candidate.size();
		
		for (LinkedList<Slot> route : routes){
			if (route.size() < best){
				candidate = route;
				best = route.size();
			}
		}
		return candidate;
	}



	private void extend(MapMatrix map, LinkedList<LinkedList<Slot>> routes,
			LinkedList<Slot> closedSlots, LinkedList<Slot> route) {
		LinkedList<Slot> sourroundingPaths, current;
		sourroundingPaths = map.sourroundingPaths(route.getLast());
		
		for (Slot slot : sourroundingPaths){
			if (!closedSlots.contains(slot)){
				current = new LinkedList<Slot>(route);
				current.add(slot);
				routes.add(current);	
				closedSlots.add(slot);
			}
		}
	}

}
